package DP.背包.万诺复习;

import org.junit.Test;

import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
全排列[每样1个] -> 去掉vis -> [每样无限]

本题靠 第2保险 mhdebug 解决的

1 2 5 100
-> 就会超时
 */
public class 无限零钱_版本1_全排列void {
    // void
    int[] vis;
    int resMinGeShu = 9999999;
    private void quanpailie(int cI, long faW, int faGeShu) {
        System.out.println(faW);
        if(faW >= W){
            if(faW == W){
                resMinGeShu = Math.min(faGeShu, resMinGeShu);
            }
            return;
        }

//        for (int i = 0; i < w.length; i++) {
        for (int i = 0; i < Math.min(w.length, resMinGeShu); i++) {
            // 全排列[每样1个] -> 去掉vis -> [每样无限]
            quanpailie(0, faW + w[i], faGeShu+1);
        }
    }


    @Test
    public void test() {
        int[] w_conis = {1,2,5};
        int W_amount = 10;
//        int[] w_conis = {1,2147483647};
//        int W_amount = 2;

        System.out.println(coinChange(w_conis, W_amount));
    }
    int[] w;
    int W;
    public int coinChange(int[] coins, int amount) {
        w=coins; W=amount;
        vis = new int[w.length];
        // 逆序排序 -> 因为我先要大硬币 全是1爆栈
//        Arrays.sort(coins);
//        Stack<Integer> stack = new Stack<>();
//        for (int coin : coins) {
//            stack.push(coin);
//        }
//        int[] rever_coins = new int[coins.length];
//        int i =0;
//        while(!stack.isEmpty()){
//            rever_coins[i++] = stack.pop();
//        }
//        w = rever_coins;

        Arrays.sort(coins);
        int[] ints = reverse_shuzu(coins);
        System.out.println(Arrays.toString(ints));

        int cI=0, faGeShu=0; // cI所有回溯都有
        long faW = 0; //防止1+MAX = -217xxx..
        quanpailie(cI, faW, faGeShu);
        return resMinGeShu;
    }
}
